package cxydmmszl.chapter09.t164;

import java.io.BufferedReader;
import java.io.InputStreamReader;

/**
 * <li style="color: red;">Prob</li>
 * 一种字符串和数字的对应关系
 * <li style="color: green;">Desc</li>
 * 一个 char 类型的数组 chs，其中所有的字符都不同。<br/>
 * 例如，chs = ['A', 'B', 'C', ... 'Z']，则字符串与整数的对应关系如下：<br/>
 * A,  B...Z, AA, AB...AZ, BA, BB...ZZ, AAA...ZZZ,   AAAA ...<br/>
 * 1,  2...26,27, 28...52, 53, 54...702,703...18278, 18279...<br/>
 * 例如，chs=['A','B','C']，则字符串与整数的对应关系如下：<br/>
 * A, B, C, AA, AB...CC, AAA...CCC, AAAA....<br/>
 * 1, 2, 3, 4 , 5 ...12, 13 ...39 , 40  ....<br/>
 * 给定一个数组 chs，实现根据对应关系完成字符串与整数相互转换的两个函数。
 * <br/><br/>[要求]<br/>
 * 数字转字符串的复杂度为 O(logN)，字符串转数字的复杂度为 O(字符串长度)
 * <li style="color: green;">Input</li>
 * 第一行有里两个个整数opt, base, 分别表示问题类型，chs的长度
 * 接下来一行有 base 个字符表示字符数组 chs。
 * 若opt = 1，则下一行有一个整数 N，分别表示对应的数字。
 * 若opt = 2，则下一行有一个字符串，表示需要转化为数字的字符数组。
 * <li style="color: green;">Output</li>
 * 若 opt=1，输出一个字符串。否则输出一个整数。
 * <li style="color: blue;">Link</li> CD71
 *
 * @author habitplus
 * @since 2021-10-13 19:14
 */
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] ss = br.readLine().split(" ");
        int opt = Integer.parseInt(ss[0]);
        int base = Integer.parseInt(ss[1]);
        String baseStr = br.readLine();

        String str = br.readLine();
        if (opt == 1) {
            int k = Integer.parseInt(str);
            str = digitalToStr(baseStr, k);
            System.out.println(str);
        } else if (opt == 2) {
            int ans = strToDigital(str, base);
            System.out.println(ans);
        }
    }

    private static String digitalToStr(String baseStr, int k) {
        if (baseStr == null || baseStr.length() < 1 || k < 1) {
            return "";
        }

        char[] chs = baseStr.toCharArray();
        int base = chs.length;
//        StringBuilder sb = new StringBuilder();
//        int t;
//        while(k > 0) {
//            k--;
//            t = k / base;
//            sb.append(chs[k % base]);
//            k = t;
//        }
//
//        return sb.reverse().toString();

        int cur = 1;
        int len = 0;
        while (k >= cur) {
            len++;
            k -= cur;
            cur *= base;
        }

        char[] res = new char[len];
        int i = 0;
        do {
            cur /= base;
            res[i++] = chs[k / cur];
            k %= cur;
        } while (i != len);

        return new String(res);
    }

    private static int strToDigital(String str, int base) {
        if (base < 1 || str == null || str.length() < 1) {
            return 0;
        }

        char[] chs = str.toCharArray();
        int n = chs.length;

        int d = 1;
        int ans = 0;
        for (int i = n - 1; i >= 0; i--) {
            ans += d * (chs[i] - 'A' + 1);
            d *= base;
        }

        return ans;
    }
}
